﻿using System;
using System.Collections.Generic;
using System.Drawing;

namespace GobangGameComponent
{
    partial class GameBoard
    {

        public class Node
        {
            public Node bestChild;
            public List<Node> child = new List<Node>();
            public Point p = new Point();
            public int mark;

            public Node()
            {
                child.Clear();
                bestChild = null;
                mark = 0;
            }

            public void setPoint(Point r)
            {
                p.X = r.X;
                p.Y = r.Y;
            }

            public void addChild(Node r)
            {
                child.Add(r);
            }

            public Node getLastChild()
            {
                return child[child.Count - 1];
            }
        }


        public Point AlphaBeta()
        {

            Node node = new Node();
            Point p = new Point();
            Dfs(0, node, MINN, MAXN, p);
            Point point = node.bestChild.p;
            //map[point.X, point.Y] = 2;
            if (toJudge.Contains(point))
            {
                toJudge.Remove(point);
            }
            for (int i = 0; i < 8; i++)
            {
                Point now = new Point(point.X + dc[i], point.Y + dr[i]);
                if (0 <= now.X && now.X < gameSize && 0 <= now.Y && now.Y < gameSize && map[now.Y, now.X] == 0)
                {
                    toJudge.Add(now);
                }
            }
            return point;
        }

        static int searchDeep = 4;
        static HashSet<Point> toJudge = new HashSet<Point>();
        public static int MAXN = 1 << 28;
        public static int MINN = -MAXN;
        static int[] dr = new int[] { -1, 1, -1, 1, 0, 0, -1, 1 }; // 方向向量  
        static int[] dc = new int[] { 1, -1, -1, 1, -1, 1, 0, 0 }; //方向向量  

        // alpha beta dfs
        // 递归函数，用于搜索棋面状态
        private static void Dfs(int deep, Node root, int alpha, int beta, Point p)
        {
            if (deep == searchDeep)
            {
                root.mark = GetMark();
                // 达到搜索深度后，计算当前节点的评分并返回
                return;
            }
            // 创建可供遍历的点集合
            List<Point> judgeSet = new List<Point>();
            foreach (var point in toJudge)
            {
                judgeSet.Add(point);
            }
            // 遍历每个待判断的点
            foreach (var now in judgeSet)
            {
                Node node = new Node();
                node.setPoint(now);
                root.addChild(node);
                bool flag = toJudge.Contains(now);
                map[now.Y, now.X] = ((deep & 1) == 1) ? 1 : 2;
                // 如果当前点满足胜利条件，则更新当前节点的评分并返回
                if (IsEnd(now.X, now.Y))
                {
                    root.bestChild = node;
                    root.mark = MAXN * map[now.Y, now.X];
                    map[now.Y, now.X] = 0;
                    return;
                }
                bool[] flags = new bool[8]; // 用于标记是否需要删除的临时标记数组
                for (int i = 0; i < 8; i++) flags[i] = true;
                for (int i = 0; i < 8; ++i)
                {
                    var next = new Point(now.X + dc[i], now.Y + dr[i]);
                    // 判断下一个点是否在棋盘范围内且为空位
                    if (0 <= now.X + dc[i] && now.X + dc[i] < gameSize && 0 <= now.Y + dr[i] && now.Y + dr[i] < gameSize
                            && map[next.Y, next.X] == 0)
                    {
                        // 若不在待判断集合中，添加到集合中；否则更新 flags 数组
                        if (!toJudge.Contains(next))
                        {
                            toJudge.Add(next);
                        }
                        else
                        {
                            flags[i] = false;
                        }
                    }
                }
                // 如果当前点在待判断集合中，移除该点
                if (flag)
                {
                    toJudge.Remove(now);
                }

                Dfs(deep + 1, root.getLastChild(), alpha, beta, now);
                map[now.Y, now.X] = 0;

                if (flag)
                {
                    toJudge.Add(now);
                }
                for (int i = 0; i < 8; ++i)
                {
                    if (flags[i])
                    {
                        toJudge.Remove(new Point(now.X + dc[i], now.Y + dr[i]));
                    }
                }

                // alpha beta剪枝
                // min层
                if ((deep & 1) == 1)
                {
                    if (root.bestChild == null || root.getLastChild().mark > root.bestChild.mark)
                    {
                        root.bestChild = root.getLastChild();
                        root.mark = root.bestChild.mark;
                        if (root.mark == MAXN)
                        {
                            root.mark -= deep;
                        }
                        alpha = Math.Max(root.mark, alpha);
                    }
                    if (root.mark >= beta)
                    {
                        return;
                    }
                }
                // max层
                else
                {

                    if (root.bestChild == null || root.getLastChild().mark < root.bestChild.mark)
                    {
                        root.bestChild = root.getLastChild();
                        root.mark = root.bestChild.mark;
                        if (root.mark <= MINN)
                        {
                            root.mark += deep;
                        }
                        beta = Math.Min(root.mark, beta);
                    }
                    if (root.mark <= alpha)
                    {
                        return;
                    }
                }
            }
            // 如果是第一层递归，输出分隔符
            // if(deep==0)
            // System.Console.WriteLine("******************************************");
        }
        public static int GetMark()
        {
            int res = 0;
            for (int i = 0; i < gameSize; ++i)
            {
                for (int j = 0; j < gameSize; ++j)
                {
                    if (map[i, j] != 0)
                    {
                        // 行
                        bool flag1 = false, flag2 = false;
                        int x = j, y = i;
                        int cnt = 1;
                        int col = x, row = y;
                        while (--col >= 0 && map[row, col] == map[y, x]) ++cnt;
                        if (col >= 0 && map[row, col] == 0) flag1 = true;
                        col = x;
                        row = y;
                        while (++col < gameSize && map[row, col] == map[y, x]) ++cnt;
                        if (col < gameSize && map[row, col] == 0) flag2 = true;
                        if (flag1 && flag2)
                            res += map[i, j] * cnt * cnt;
                        else if (flag1 || flag2) res += map[i, j] * cnt * cnt / 4;
                        if (cnt >= 5) res = MAXN * map[i, j];
                        // 列
                        col = x;
                        row = y;
                        cnt = 1;
                        flag1 = false;
                        flag2 = false;
                        while (--row >= 0 && map[row, col] == map[y, x]) ++cnt;
                        if (row >= 0 && map[row, col] == 0) flag1 = true;
                        col = x;
                        row = y;
                        while (++row < gameSize && map[row, col] == map[y, x]) ++cnt;
                        if (row < gameSize && map[row, col] == 0) flag2 = true;
                        if (flag1 && flag2)
                            res += map[i, j] * cnt * cnt;
                        else if (flag1 || flag2)
                            res += map[i, j] * cnt * cnt / 4;
                        if (cnt >= 5) res = MAXN * map[i, j];
                        // 左对角线
                        col = x;
                        row = y;
                        cnt = 1;
                        flag1 = false;
                        flag2 = false;
                        while (--col >= 0 && --row >= 0 && map[row, col] == map[y, x]) ++cnt;
                        if (col >= 0 && row >= 0 && map[row, col] == 0) flag1 = true;
                        col = x;
                        row = y;
                        while (++col < gameSize && ++row < gameSize && map[row, col] == map[y, x]) ++cnt;
                        if (col < gameSize && row < gameSize && map[row, col] == 0) flag2 = true;
                        if (flag1 && flag2)
                            res += map[i, j] * cnt * cnt;
                        else if (flag1 || flag2) res += map[i, j] * cnt * cnt / 4;
                        if (cnt >= 5) res = MAXN * map[i, j];
                        // 右对角线
                        col = x;
                        row = y;
                        cnt = 1;
                        flag1 = false;
                        flag2 = false;
                        while (++row < gameSize && --col >= 0 && map[row, col] == map[y, x]) ++cnt;
                        if (row < gameSize && col >= 0 && map[row, col] == 0) flag1 = true;
                        col = x;
                        row = y;
                        while (--row >= 0 && ++col < gameSize && map[row, col] == map[y, x]) ++cnt;
                        if (row >= 0 && col < gameSize && map[i, j] == 0) flag2 = true;
                        if (flag1 && flag2)
                            res += map[i, j] * cnt * cnt;
                        else if (flag1 || flag2) res += map[i, j] * cnt * cnt / 4;
                        if (cnt >= 5) res = MAXN * map[i, j];
                    }
                }
            }
            return res;
        }


        public static bool IsFinished = false;
        public static bool IsEnd(int x, int y)
        {
            // 判断一行是否五子连珠
            int cnt = 1;
            int col = x, row = y;
            while (--col > 0 && map[row, col] == map[y, x]) ++cnt;
            col = x;
            row = y;
            while (++col < gameSize && map[row, col] == map[y, x]) ++cnt;
            if (cnt >= 5)
            {
                IsFinished = true;
                return true;
            }
            // 判断一列是否五子连珠
            col = x;
            row = y;
            cnt = 1;
            while (--row > 0 && map[row, col] == map[y, x]) ++cnt;
            col = x;
            row = y;
            while (++row < gameSize && map[row, col] == map[y, x]) ++cnt;
            if (cnt >= 5)
            {
                IsFinished = true;
                return true;
            }
            // 判断左对角线是否五子连珠
            col = x;
            row = y;
            cnt = 1;
            while (--col > 0 && --row > 0 && map[row, col] == map[y, x]) ++cnt;
            col = x;
            row = y;
            while (++col < gameSize && ++row < gameSize && map[row, col] == map[y, x]) ++cnt;
            if (cnt >= 5)
            {
                IsFinished = true;
                return true;
            }
            // 判断右对角线是否五子连珠
            col = x;
            row = y;
            cnt = 1;
            while (++row < gameSize && --col >= 0 && map[row, col] == map[y, x]) ++cnt;
            col = x;
            row = y;
            while (--row >= 0 && ++col < gameSize && map[row, col] == map[y, x]) ++cnt;
            if (cnt >= 5)
            {
                IsFinished = true;
                return true;
            }
            return false;
        }
    }
}
